//
// Created by Snow on 2023/5/15.
//
//快速排序算法
#include"seqlist.cpp"
//填坑法
int partition(RecType R[],int s,int t)//一趟划分
{
    int i=s,j=t;
    RecType base=R[i];//以R[i]为基准
    while(i<j)//从两端交替向中间扫描，直到i=j为止
    {
        while(j>i&&R[j].key>=base.key)
            j--;//从右向左扫描,找一个小于tmp.key的R[j]
        if(i<j)
        {
            R[i]=R[j];
            i++;
        }
        while(i<j&&R[i].key<=base.key)
            i++;//从左向右扫描,找一个大于tmp.key的R[i]
        if(i<j)
        {
            R[j]=R[i];
            j--;
        }
    }
    R[i]=base;
    return i;
}
void QuickSort(RecType R[],int s,int t)//对R[s..t]的元素进行快速排序
{
    int i;
    if(s<t)//区间内至少存在两个元素的情况
    {
        i=partition(R,s,t);
        QuickSort(R,s,i-1);//对左区间递归排序
        QuickSort(R,i+1,t);//对右区间递归排序
    }
}
int main()
{
	int n=10;
	RecType R[MAXL];
	KeyType a[]={15,18,29,12,35,32,27,23,10,20};
	CreateList(R,a,n);
	DispList(R,n);
	QuickSort(R,0,n-1);
    DispList(R,n);
	return 1;
}

//int main()
//{
//    int n=10;
//    RecType R[MAXL];
//    KeyType a[]={6,8,7,9,0,1,3,2,4,5};
//    CreateList(R,a,n);
//    DispList(R,n);
//    QuickSort(R,0,n-1);
//    DispList(R,n);
//    return 1;
//}